Hello 2023

新年快乐~

比赛链接：https://codeforces.com/contest/1779

A. Hall of Fame

题解

构造 RL 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string s;
        cin >> s;

        if ((int)set(s.begin(), s.end()).size() == 1) {
            cout << -1 << "\n";
            continue;
        }

        if (s.find("RL") != string::npos) {
            cout << 0 << "\n";
        } else {
            for (int i = 0; i + 1 < n; i++) {
                if (s[i] == 'L' and s[i + 1] == 'R') {
                    cout << i + 1 << "\n";
                    break;
                }
            }
        }
    }

    return 0;
}

B. MKnez’s ConstructiveForces Task

题解

当 $n$ 为偶数时，构造 $-1， 1$ 即可。

当 $n$ 为奇数时，以 $n = 5$ 为例，当 $i = 1, 2, 3, 4$ 时，有：

$s_3 + s_4 + s_5 = 0$

$s_1 + s_4 + s_5 = 0$

$s_1 + s_2 + s_5 = 0$

$s_1 + s_2 + s_3= 0$

相邻等式相减得：

$s_1 = s_3 = s_5$

$s_2 = s_4$

即在 $s$ 中，奇数项与偶数项的值各自相同。

设奇数项的值为 $a$ ，偶数项的值为 $b$ ，根据题设，有：

$\frac{(n + 1)}{2}a + \frac{(n - 1)}{2}b = a + b$

化简得： $(n - 1)a = -(n - 3)b$

所以令 $a = -(n - 3), b = (n - 1)$ 即可，由于 $s_i \ne 0$ ，故 $n = 3$ 时无解。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        if (n & 1) {
            if (n == 3) {
                cout << "NO" << "\n";
            } else {
                cout << "YES" << "\n";
                for (int i = 0; i < n; i++) {
                    cout << (i & 1 ? (n - 1) : -(n - 3)) << " \n"[i == n - 1];
                }
            }
        } else {
            cout << "YES" << "\n";
            for (int i = 0; i < n; i++) {
                cout << (i & 1 ? 1 : -1) << " \n"[i == n - 1];
            }
        }

    }

    return 0;
}

C. Least Prefix Sum

题解

因为 $a_1 + a_2 + \dots + a_m$ 是最小的前缀和之一，所以：

• 以 $a_m$ 为右端点的后缀和不能大于 $0$
• 以 $a_{m + 1}$ 为左端点的前缀和不能小于 $0$

注意在后缀和中，左端点最多取到 $a_2$ ，不能取到 $a_1$ 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int ans = 0;
        {
            priority_queue<int> pque;
            long long sum = 0;
            for (int i = m - 1; i > 0; i--) {
                sum += a[i];
                if (a[i] > 0) {
                    pque.push(a[i]);
                }
                while (sum > 0) {
                    int x = pque.top();
                    pque.pop();
                    sum -= 2 * x;
                    ans += 1;
                }
            }
        }
        {
            priority_queue<int, vector<int>, greater<int>> pque;
            long long sum = 0;
            for (int i = m; i < n; i++) {
                sum += a[i];
                if (a[i] < 0) {
                    pque.push(a[i]);
                }
                while (sum < 0) {
                    int x = pque.top();
                    pque.pop();
                    sum -= 2 * x;
                    ans += 1;
                }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

D. Boris and His Amazing Haircut

题解

如果有 $a_i < b_i$ ，则无解。

否则，对于每个不相等的 $a_i, b_i$ ，查询最右端不大于 $b_i$ 的值 $b_j$ ，将下标区间 $[i, j]$ 中值为 $b_i$ 的数都标记为访问过即可。

查询区间内第一个大于 $b_i$ 的数可以用线段树，查询区间内值为 $b_i$ 的数的下标可以用 map<int, queue<int>> 。

代码

#include <bits/stdc++.h>
using namespace std;

#define ls (o<<1)
#define rs ((o<<1)|1)
#define mid ((l+r)>>1)

const int N = 2e5 + 100;
int tree[4 * N];

void build(int o, int l, int r, vector<int>& b) {
    if (l == r) {
        tree[o] = b[l - 1];
        return;
    }
    build(ls, l, mid, b);
    build(rs, mid + 1, r, b);
    tree[o] = max(tree[ls], tree[rs]);
}

int get(int o, int l, int r, int x) {
    if (l == r) return l;
    return tree[ls] > x ? get(ls, l, mid, x) : get(rs, mid+1, r, x);
}

int query(int o, int l, int r, int ql, int qr, int x) { //查询[ql, qr]内第一个大于 x 的数的位置
    if (qr < l || r < ql) return -1;
    if (ql <= l && r <= qr) return tree[o] > x ? get(o, l, r, x) : -1;
    int t = query(ls, l, mid, ql, qr, x);
    return t != -1 ? t : query(rs, mid + 1, r, ql, qr, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<int> b(n);
        map<int, queue<int>> mp;
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            mp[b[i]].push(i);
        }

        build(1, 1, n, b);

        int m;
        cin >> m;

        vector<int> x(m);
        for (int i = 0; i < m; i++) {
            cin >> x[i];
        }

        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (a[i] < b[i]) {
                ok = false;
                break;
            }
        }

        multiset<int> mst(x.begin(), x.end());
        vector<bool> vis(n);

        for (int i = 0; i < n; i++) {
            if (vis[i]) {
                continue;
            }
            if (a[i] != b[i]) {
                if (mst.find(b[i]) == mst.end()) {
                    ok = false;
                    break;
                } else {
                    mst.erase(mst.find(b[i]));
                }
                int r = query(1, 1, n, i + 1, n, b[i]);
                r = (r == -1 ? n : r - 1);
                while (not mp[b[i]].empty() and mp[b[i]].front() < r) {
                    vis[mp[b[i]].front()] = true;
                    mp[b[i]].pop();
                }
            }
        }

        cout << (ok ? "YES" : "NO") << "\n";
    }

    return 0;
}